Given a sequence X={x1,x2,…,xn} with n non-negative numbers and a positive integer k≤n, the linear partition problem requires to partition X into k or less than k subsequences, so as to minimize the maximum sum of elements over all subsequences. The known best algorithm for this problem is a dynamic programming algorithm with time complexity O(kn2) and space complexity O(kn). By using the properties of the non-negative sequence, an improved algorithm with time complexity O(knlogn) and space complexity O(n) was given.